package com.sam;

import static java.lang.Long.MAX_VALUE;

/**
 * 汉诺塔问题
 *
 * 汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，
 * 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
 * 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
 *
 * https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295?fr=aladdin
 *
 * Created by samwang on 2017/11/24.
 */
public class Hanoi {
    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
        System.out.println("args = " + MAX_VALUE );

    }

    /**
     *
     * @param n 共N个盘子； 需要移动的次数 2^n -1
     * @param src 源坐
     * @param mid 中转座
     * @param dest 目标座
     */
    static void hanoi(int n, char src, char mid, char dest) {
        if (n == 1) {//只需要移动一次
            System.out.println(src + " -> " + dest);
        } else {
            hanoi(n - 1, src, dest, mid);//先把N-1移到中间
            System.out.println(src + " -> " + dest);//再把第N个移到dest
            hanoi(n - 1, mid, src, dest);//把N-1个移到dest
        }
    }

}
